Frieren and Rotating Calipers
Frieren and Rotating Calipers
时间限制:1s
空间限制:256MB
Description
芙莉莲正在学习旋转卡壳,但是字不会念,你能告诉她正确的读音吗?
学习过程中看到最小矩形覆盖问题,即给你n个点,求最小的矩形使得覆盖所有点。她发现最小的矩形的长和宽不一定与$x$轴,$y$轴平行,她认为这些矩形非常无聊,你能找到面积最小的有趣矩形使得覆盖所有点吗?
有趣矩形:长和宽与$x$轴或$y$轴平行的矩形
Input Description
第一行一个正整数T表示测试数 $1 \le T \le 10^2$
每个测试的第一行有一个正整数n表示点的数量 $1 \le n \le 10^4$
每个测试接下来有n行,每行两个整数 $(x, y) $ $0 \le x \le 10^4 $,$0 \le y \le 10^4 $
Output Description
每行输出符合条件的有趣矩形的面积
Input Sample
1 | 2 |
Output Sample
1 | 1 |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 GitSteve1025!